With increasing progress and popularity of network communications and e-commerce in recent years, it has become very important to achieve high security in communication. One method to achieve high security is to use encryption in communication, and many encryption techniques are used in actual communication systems.
For example, there is a known system in which a cryptographic processing module is disposed in a small-sized apparatus such as an IC card whereby, when data is transmitted between the IC card and a data reader/writer, processing including authentication and encryption/decryption of data is performed.
Various cryptographic algorithms are known. They can be roughly classified into public hey cryptography and common key cryptography. In the public key cryptography, different keys are used for encryption and decryption. For example, a public key is used for encryption, and a private key is used for decryption. In the common key cryptography, the same key is used for encryption and decryption.
Various algorithms of common key cryptography are known. In one of such algorithms, a plurality of keys are produced based on a common key, and a data transformation is performed repeatedly in units of blocks (each block including, for example, 64 bits or 128 bits) using the produced keys. Common key block cryptography is a typical example of cryptography using such an algorithm including producing keys and perforating data transformation.
A typical common key encryption scheme is that according to the DES (Data Encryption Standard) adopted as one of Federal Information Processing Standards, and is widely used in various fields.
Common key block encryption algorithms typified by the DES algorithm include two main parts. One part is a round function which transforms input data, and the other part is a key schedule which produces keys used in respective rounds by the round function (F-function). Round keys (subkeys) used in respective rounds of the round function are produced by the key schedule part on the basis of a single master key input to the key schedule part, and used in the respective rounds of the round function.
A problem with the common key cryptography is leakage of keys by cryptanalysis. In a typical method of an attack or a cryptanalysis, a great number of input data (plaintext) having particular differences and corresponding output data (ciphertext) are analyzed to find keys used in respective round functions (this method is known as a differential cryptanalysis or a differential attack). It is also known to perform a cryptanalysis based on plaintext and corresponding ciphertext (this method is known as a linear cryptanalysis or a linear attack).
If a key used to produce a cipher can be easily found via a cryptanalysis, the cipher cannot be high in security. In conventional DES algorithms, a process performed by a linear transformation part of a round function (function) is the same for all rounds (that is, the same transformation matrix is used for all rounds). This makes it possible to easily analyze the algorithm and thus easily find keys.